| class DIGRAPH{NTP} < $DIGRAPH{NTP},$SUPPORTS_REHASH |
|---|
| **** | This is a directed graph which permits arbitrary nodes of type NTP. This is the default graph implementation. NTP is the node type i.e the unique node index The actual nodes of the graph may be supplied by the user of this class, during the add_node. The digraph is implemented by two hash mappings from nodes to parents and nodes to outgoing. There is also a separate list of nodes. |
| $SUPPORTS_REHASH | $DIGRAPH{_} | $RO_DIGRAPH{_} | $GRAPH{_,_} | $STR | $ELT{_} | $ELT | DIGRAPH_INCL{_} | RO_DIGRAPH_INCL{_} | COMPARE{_} |
| LBLD_DIGRAPH{_,_,_} | WTD_DIGRAPH{_,_} |
| add_node(n: NTP) |
|---|
| **** | Short hand for "add_node(n:NTP): NTP" that is only valid for this sort of graph, where the user specifies the node type. |
| add_node(n: NTP): NTP |
|---|
| **** | Add the node "n". In this kind of hash digraph, the node index returned is guaranteed to be the same as the node "n". Note that this is not generally true for graphs |
| add_node: NTP |
|---|
| **** | Add a new node and return the index |
| connect(e: DIEDGE{NTP}) |
|---|
| **** | Connect source to target. No change if the edge already exists Add the nodes if they do not exist |
| connect(f,s: NTP) .. Included as connect |
|---|
| connect(f,s: NTP): SAME .. Included as connect |
|---|
| copy: $DIGRAPH{NTP} .. Included as copy |
|---|
| create(node_gen: $SUCC_STREAM{NTP}): SAME |
|---|
| **** | Create a new digraph. Store "node_gen" as a generator of nodes, so that when "add_node: NTP" is called it can generate unique new nodes. |
| create: SAME |
|---|
| **** | Create a new digraph and return it. Since a node generator is not specified, it will not be possible to call the "add_node:NTP" function, since the graph will not know how to create new unique nodes. All the data structures can be initialized with void |
| delete_node(n: NTP) |
|---|
| **** | Delete a node from the graph, and all its accompanying edges |
| disconnect(e: DIEDGE{NTP}) |
|---|
| **** | Deletes the edge "e". |
| disconnect(f,s: NTP) .. Included as disconnect |
|---|
| equals(g: $RO_DIGRAPH{NTP}):BOOL .. Included as equals |
|---|
| **** | True if both have the same set of nodes and edges |
| has(n: NTP): BOOL .. Included as has |
|---|
| has_edge(e: DIEDGE{NTP}): BOOL |
|---|
| has_node(n: NTP): BOOL |
|---|
| is_empty: BOOL .. Included as is_empty |
|---|
| is_identical(g: SAME): BOOL |
|---|
| **** | Check whether the two graphs have the same nodes, edges in the same order |
| is_topo_order(n: $ARR{NTP}):BOOL |
|---|
| **** | Return true if the nodes in "n" do not violate the precedence relations expressed by the graph "self" |
| n_adjacent(n:NTP): INT .. Included as n_adjacent |
|---|
| n_edges: INT |
|---|
| **** | Returns the number of edges in the graph, making sure each edge is only counted once |
| n_incoming(n: NTP): INT |
|---|
| **** | Number of incoming edges from node "n" |
| n_neighbors(n: NTP): INT |
|---|
| **** | Returns the number of neighbors of "n" (nodes are only counted once) |
| n_nodes: INT |
|---|
| n_outgoing(n: NTP): INT |
|---|
| **** | Number of outgoing edges from node "n" |
| elt_eq(e1,e2:ETP):BOOL .. Included as node_equal |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| rehash |
|---|
| size: INT .. Included as size |
|---|
| str: STR .. Included as str |
|---|
| **** | Print out the graph using the bound routine "f" for the nodes |
| adjacent!(once n: NTP): NTP .. Included as adjacent! |
|---|
| **** | Adjacent is aliased to "outgoing" |
| bf!(once n: NTP): NTP |
|---|
| **** | Yield all nodes in breadth first order |
| df!(once n: NTP): NTP |
|---|
| **** | Yield all nodes in depth first order |
| edge!: DIEDGE{NTP} |
|---|
| **** | Return all edges in the graph |
| elt!: NTP .. Included as elt! |
|---|
| **** | Returns the nodes of the graph |
| incoming!(once n: NTP): NTP |
|---|
| layer!: SET{NTP} |
|---|
| **** | Peel off successive layers from the graph, starting with the root set. Stop when no more roots (nodes with no incoming edges) can be found. |
| node!: NTP |
|---|
| outgoing!(once n: NTP): NTP |
|---|
| sink!: NTP |
|---|
| **** | Yield all the sink nodes (with n_outgoing = 0) in self |
| source!: NTP |
|---|
| **** | Yield all the source nodes with n_incoming = 0 in self |
| topo_order!: NTP |
|---|
| **** | Yield the nodes of self in some topologically sorted orer |
| check_node(n: NTP,routine_name: STR): BOOL |
|---|
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| attr incoming_map: FMULTIMAP{NTP,NTP}; |
|---|
| attr incoming_map: FMULTIMAP{NTP,NTP}; |
|---|
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| attr node_generator: $SUCC_STREAM{NTP}; |
|---|
| **** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
| attr node_generator: $SUCC_STREAM{NTP}; |
|---|
| **** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
| attr node_list: FLIST{NTP}; |
|---|
| **** | List of nodes in the graph |
| attr node_list: FLIST{NTP}; |
|---|
| **** | List of nodes in the graph |
| node_str(n: NTP): STR .. Included as node_str |
|---|
| **** | There should not be void nodes in the graph! |
| attr outgoing_map: FMULTIMAP{NTP,NTP}; |
|---|
| **** | Keep both around since it is quite expensive to derive one from the other. |
| attr outgoing_map: FMULTIMAP{NTP,NTP}; |
|---|
| **** | Keep both around since it is quite expensive to derive one from the other. |